1. Field of the Invention
This invention relates to the field of integrated circuits and, more particularly, to the allocation of global clock networks to physical clock regions of a programmable logic device.
2. Description of the Related Art
Modern programmable logic devices (PLDs), and particularly field programmable gate arrays (FPGAs), utilize a plurality of optimized global clock trees. Global clock trees also can be referred to as differential global clock trees, global clock lines, matched skew global clock lines, global clock interconnects, global clock network resources, or global clock spines. In any case, these global clock trees are responsible for reliably clocking sequential logic components of the PLD. Global clock trees require a significant amount of device area, or silicon, to implement and also require a substantial amount of operating power in the field. In consequence, most FPGAs include a limited number of global clock trees. The trend in modern circuit design, however, is tending toward the use of increased numbers of global clock networks in circuit designs.
The concept of clock regions was introduced to circuit design as a mechanism for dealing with the high cost of implementing global clock trees and the demand for more global clock networks per device. Clock regions are non-overlapping areas of a PLD which, typically, are rectangular in shape. Each clock region can accommodate a fixed number of logic components and support a fixed number of global clock trees. The number of global clock trees supported by a clock region usually is less than the available global clock drivers within the PLD.
In illustration, a Virtex™-4 FPGA from Xilinx, Inc. of San Jose, Calif., has clock regions of fixed dimensions. In terms of size, the clock regions span 16 configurable logic blocks (CLBs) in height and half of the die in width. By fixing the dimensions of the clock regions, larger Virtex™-4 devices can have a greater number of clock regions. With a greater number of clock regions, Virtex™-4 devices can support a greater number of multi-clock domains than otherwise would be possible.
In general, only a subset of the total clock drivers of a PLD can be included within a given clock region. Thus, only the clock drivers associated with a given clock region are available to drive global clock trees within that clock region. The number of global clock drivers “k” that can be included within each clock region of a device is largely device-architecture dependent. Thus, for a given device architecture, a “k-clock” policy can be specified which allows only “k” clock drivers to drive the global clock trees within a given clock region. Again referring to the Virtex™-4 FPGA, this device has 8 global clock trees per clock region. Any 8 of the 32 clock drivers of the device can be used to drive the global clock trees in a given clock region.
Once clock drivers are allocated, sequential circuit elements must be assigned to the clock regions. The circuit elements must be assigned in a manner that complies with the logic capacity of each clock region as well as the k-clock constraints for the device. This process is referred to as the “clock placement problem”. The clock placement problem is believed to be an NP-Complete problem. In computational complexity theory, Non-deterministic Polynomial time (NP) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine.
Conventional techniques for solving the clock placement problem are based upon approximation algorithms or heuristic algorithms. Generally, approximation and heuristic algorithms can find a sub-optimal solution for a given problem in a relatively short time period. Unlike heuristic algorithms, approximation algorithms can operate within provable runtime bounds and provide a result that has a provable quality. Both approaches, however, are non-exact and often fail to produce a feasible solution for the clock placement problem. In consequence, PLD designers usually perform a manual floor-planning for the circuit design, which is cumbersome and time-consuming. With designs continuing to utilize larger numbers of global clock networks, clock placement is likely to become a hindrance to rapid circuit design.
It would be beneficial to provide a technique for addressing the clock placement problem which overcomes the limitations described above.